# 回文链表


class Soluton:

    def middleNode(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        
        return slow
    
    def reverseList(self, head):

        pre, cur = None, head

        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        return pre


    def isPalindrome(self, head):
        # 先找出链表的中间节点
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)

        while head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next

        
        return True




